package leetcode.D900.T889;

import util.TreeNode;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-15 16:39:54 星期二
 */

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, postorder, 0, preorder.length-1, 0, postorder.length-1);
    }

    private TreeNode build(int[] preorder, int[] postorder, int prel, int prer, int postl, int postr) {
        if (prel > prer)
            return null;
        if (prel == prer)
            return new TreeNode(preorder[prel]);

        TreeNode root = new TreeNode(preorder[prel]);

        // 这里preorder[prel+1]不一定是左子树的根节点，因为左子树可能为null，那么preorder[prel+1]就是右子树根节点了
        // 由于无法判断，所以根据先序和后序，是无法唯一确定二叉树的
        int k = 0, leftRoot = preorder[prel+1];
        for(int i=postl; i<postr; ++i) {
            if (postorder[i] == leftRoot) {
                k = i;
                break;
            }
        }
        root.left = build(preorder, postorder, prel+1, prel+k-postl+1, postl, k);
        root.right = build(preorder, postorder, prel+k-postl+2, prer, k+1, postr-1);
        return root;
    }
}